package com.njupt.backtracking;


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/12 11:05
 * @Description: 22. 括号生成
 * @Version: 1.0
 */


public class GenerateParenthesis_22 {


    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    /**
     * 暴力法 枚举所有的可能然后筛选符合的条件
     *
     * @param chars
     * @param position
     * @param results
     */
    private void generateAll(char[] chars, int position, List<String> results) {

        if (position == chars.length) {
            if (isValid(chars)) {
                results.add(new String(chars));
            }
        } else {
            chars[position] = '(';
            generateAll(chars, position + 1, results);
            chars[position] = ')';
            generateAll(chars, position + 1, results);
        }
    }

    private boolean isValid1(char[] chars) {
        int balance = 0;
        for (char c : chars) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    private boolean isValid(char[] chars) {
        Deque<Character> stack = new LinkedList<>();

        for (char c : chars) {
            if (c == '(') {
                stack.push(')');
            } else {
                if (stack.isEmpty() || stack.peek() != c) {
                    return false;
                } else { //stack.peek() == c
                    stack.pop();
                }

            }

        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        GenerateParenthesis_22 test = new GenerateParenthesis_22();
        List<String> strings = test.generateParenthesis(3);
        System.out.println(strings);


    }


}
